// 31. 下一个排列/nextPermutation实现
// https://leetcode.cn/problems/next-permutation/
// 标准的 “下一个排列” 算法可以描述为：
// 1.从后向前 查找第一个 相邻升序 的元素对 (i,j)，
// 满足 A[i] < A[j]。此时 [j,end) 必然是降序
// 2.在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。
// A[i]、A[k] 分别就是上文所说的「小数」、「大数」
// 3.将 A[i] 与 A[k] 交换
// 4.可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
// 5.如果在步骤 1 找不到符合的相邻元素对，
// 说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
// 该方法支持数据重复，且在 C++ STL 中被采用。

// 1,2,3,4,6,5
//       ^ ^
//   <<<<<<<<<

//1. 倒序遍历, 找到第一个数, 这个数比后面的数小;
//2. 继续倒序遍历, 找到一个比上面的数大的数;
//3. 交换
//4. 把1中的这个数后面的数全部递增排列,
// 因为在1后面的数时递减排列的, 
// 所以首尾交换即可获得升序排列


#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif
#include <bits/stdc++.h>
using namespace std;

class Solution {
  public:
  void nextPermutation(vector<int>& nums) {
      int i=nums.size()-2;      
      for(; i>=0&&nums[i]>=nums[i+1]; i--);
      if(i>=0){
          int j=nums.size()-1;
          for(;j>=0&&nums[j]<=nums[i];j--);
          swap(nums[i],nums[j]);
      }
      reverse(nums.begin()+i+1,nums.end());
  }
  
  void nextPermutation_stl(vector<int>& nums) {
    next_permutation(nums.begin(), nums.end());
  }
};

int main() {
  Solution sol;
  vector<int> nums = {1,5,4,9};
  sol.nextPermutation_1(nums);
  for (auto nn : nums) PF("%d,", nn);
  PF("\n");
  return 0;
}

